package 康复训练_JavaGo并驾齐驱;

import java.util.HashMap;
import java.util.Map;

public class Jz35复杂链表的复制 {

    /**
     * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，
     * 每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
     */

    public Node copyRandomList(Node head) {

        if (head == null) {
            return null;
        }

        // 待优化: 一个Map直接 Node-Node 对应即可
        Map<Node, Integer> mapA = new HashMap<>();
        Map<Integer, Node> mapB = new HashMap<>();

        Node newHead = new Node(head.val);
        Node sourceNode = head;
        Node newNode = newHead;
        int index = 0;

        while (true) {
            mapA.put(sourceNode, index);
            mapB.put(index, newNode);
            index++;

            Node next = sourceNode.next;
            if (next == null) {
                break;
            }
            newNode.next = new Node(next.val);
            newNode = newNode.next;

            sourceNode = sourceNode.next;
        }

        sourceNode = head;
        newNode = newHead;
        while (sourceNode != null) {
            if (sourceNode.random != null) {
                int sourceNodeIndex = mapA.get(sourceNode.random);
                newNode.random = mapB.get(sourceNodeIndex);
            }
            sourceNode = sourceNode.next;
            newNode = newNode.next;
        }

        return newHead;
    }

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public static void main(String[] args) {
        Jz35复杂链表的复制 n = new Jz35复杂链表的复制();
    }

}
